/* 在二叉树中查找值为x的结点，打印出值为x的所有祖先 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 打印特定结点的所有祖先 -- 后序遍历，找到x
void Nonpost(BTNode *bt, char x)
{
  // 创建栈
  BTNode *St[maxsize], *tag = NULL;
  int top = -1;
  
  // 栈不为空 或者 访问的结点不为空
  while (bt || top != -1)
  {
    // 访问的结点不为空
    if (bt != NULL)
    {
      // 进栈
      St[++top] = bt;
      
      // 到左孩子结点
      bt = bt->lchild;
    }
    
    // 访问的结点为空
    else
    {
      // 取栈顶元素
      bt = St[top];
      
      // 如果存在右孩子 并且 右孩子没有被访问过
      if (bt->rchild && bt->rchild != tag)
        bt = bt->rchild; // 到右孩子
      
      // 否则
      else
      {
        // 出栈
        bt = St[top--];
        
        // 如果元素为x
        if (bt->data == x)
          while (top != -1) // 栈内元素全部出栈
            cout << St[top--]->data << " ";
            
        // 记录上一次访问的结点
        tag = bt;
        bt = NULL;
      }
    }
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 打印特定结点的所有祖先
  Nonpost(T, '5');
}